Mục đích của bảng là cho phép thuật toán so sánh mỗi ký tự của S không quá một lần. Sự quan sát chìa khóa về bản chất của phương pháp tìm kiếm tuyến tính cho phép điều này xảy ra là trong quá trình so sánh các đoạn của chuỗi chính với đoạn mở đầu của mẫu, chúng ta biết chính xác được những vị trí mà đoạn mẫu có thể xuất hiện trước vị trí hiện tại. Nói cách khác, chúng ta "tự tìm kiếm" đoạn mẫu trước và đưa ra một danh sách các vị trí trước đó mà bỏ qua tới các ký tự vô vọng mà vẫn không mất đi các đoạn tiềm năng.

Chúng ta muốn tìm kiếm, với mỗi vị trí trên W, độ dài của đoạn dài nhất giống với "đoạn bắt đầu" trên W tính đến (không bao gồm) vị trí đó, đây là khoảng cách chúng ta có thể lùi lại để tiếp tục so khớp. Do vậy T[i] là giá trị của độ dài đoạn dài nhất kết thúc bởi phần tử W[i - 1]. Chúng ta sử dụng quy ước rằng một chuỗi rỗng có độ dài là 0. Với trường hợp không trùng với mẫu ngay ở giá trị đầu tiên (không có khả năng lùi lại), ta gán T[0] = -1.

Ví dụ cho thuật toán xây dựng bảng

Ta xét xâu W = "ABCDABD". Ta sẽ thấy thuật toán xây dựng bảng có nhiều nét tương đồng với thuật toán tìm kiếm chính. Ta gán T[0] = -1. Để tính T[1], ta cần tìm ra một xâu con "A" đồng thời cũng là xâu con bắt đầu của W. Vì vậy ta gán T[1] = 0. Tương tự, T[2] = 0 và T[3] = 0.

Ta xét đến ký tự W[4], 'A'. Dễ thấy ký tự này trùng với ký tự bắt đầu xâu W[0]. Nhưng do T[i] là độ dài xâu dài nhất trùng với xâu con bắt đầu trong W tính đến W[i – 1] nên T[4] = 0 và T[5] = 1. Tương tự, ký tự W[5] trùng với ký tự W[1] nên T[6] = 2.

Vì vậy ta có bảng sau:

Một ví dụ khác phức tạp hơn

Mã giả của thuật toán tạo bảng

Ví dụ ở trên đã mô tả kỹ thuật tổng quát để tạo bảng.

Dưới đây là đoạn mã giả

algorithm kmp_table:  input:    mảng ký tự, W     mảng số nguyên, T   output:    mảng T  define variables:    biến kiểu nguyên, pos ← 2     biến kiểu nguyên, cnd ← 0   let T[0] ← -1, T[1] ← 0   while pos nhỏ hơn độ dài của W, do:    (trường hợp một: tiếp tục dãy con)    if W[pos - 1] = W[cnd], 
     let T[pos] ← cnd + 1, pos ← pos + 1, cnd ← cnd + 1    (trường hợp hai: không thỏa mãn, nhưng ta có thể quay ngược trở lại)    otherwise, if cnd > 0, let cnd ← T[cnd]    (trường hợp ba: hết phần tử. Chú ý rằng cnd = 0)    otherwise, let T[pos] ← 0, pos ← pos + 1

Độ phức tạp của thuật toán tạo bảng

Độ phức tạp của thuật toán tạo bảng là O(n), với n là độ dài của W. Ngoại trừ một số sắp xếp ban đầu, toàn bộ công việc được thực hiện trong vòng lặp while, độ phức tạp của toàn bộ vòng lặp là O(n), với việc cùng lúc xử lý giá trị của pos và pos - cnd. Trong trường hợp thứ nhất, pos - cnd không thay đổi, khi cả pos và cnd cùng tăng lên một đơn vị. Ở trường hợp hai, cnd được thay thế bởi T[cnd], như chúng ta đã biết ở trên, luôn luôn nhỏ hơn cnd, do đó tăng giá trị của pos - cnd. Trong trường hợp thứ ba, pos tăng và cnd thì không, nên cả giá trị của pos và pos - cnd đều tăng. Mà pos ≥ pos - cnd, điều này có nghĩa là ở mỗi bước hoặc pos hoặc chặn dưới pos đều tăng; mà thuật toán kết thúc khi pos = n, nên nó phải kết thúc tối đa sau 2n vòng lặp, do pos - cnd bắt đầu với giá trị 1. Vì vậy độ phức tạp của thuật toán xây dựng bảng là O(n).